1. Field of the Invention
The present invention relates generally to the field of computation, and more particularly relates to methods and apparatus for computation useful for high-speed networking and communication systems.
2. Background Information
With advances in integrated circuit, microprocessor, networking and communication technologies, an increasing number of devices, in particular, digital computing devices, are being networked together. Such devices are often first coupled to a local area network, such as an Ethernet based office/home network. In turn, the local area networks are interconnected together through wide area networks, such as Synchronous Optical Networks (SONET), Asynchronous Transfer Mode (ATM) networks, Frame Relays, and the like. Of particular importance is the TCP/IP based global inter-network, the Internet. The rapid growth of the Internet has fueled a convergence of data communication (datacom) and telecommunication (telecom) protocols and requirements. It is increasingly important that data traffic be carried efficiently across local, regional and wide area networks.
As a result of this trend of increased connectivity, an increasing number of applications that are network dependent are being deployed. Examples of these network dependent applications include, but are not limited to, the World Wide Web, email, Internet based telephony, and various types of e-commerce and enterprise applications. The success of many content/service providers as well as commerce sites depends on high-speed delivery of a large volume of data across wide areas. In turn, this trend leads to an increased demand for high-speed data trafficking equipment, such as high-speed optical-electrical routers or switches and so forth. In other words, as a widening variety of new and traditional services converge across shared inter-networking transport structures, there is a critical need for the Internet to simultaneously deliver higher bandwidths, more reliable service and greater deployment flexibility. One solution for these converging services, such as that provided by Network Elements, Inc., of Beaverton, Or., is to provide highly configurable optical networking modules for efficiently interconnecting high-performance routing/switching systems in the high-speed optics-based, multi-protocol Internet infrastructure.
However, even with the advent of highly configurable optical networking modules for efficiently interconnecting high-performance routing/switching systems in the high-speed optics-based, multi-protocol Internet infrastructure, the demands for greater throughput in the future dictate that additional methods and apparatus be developed for providing greater throughput, functionality, and reliability while reducing the complexity and power consumption of such equipment. One of the functions currently handled by such networking equipment in the performance of their tasks is that of multi-precision integer division. Multi-precision integer division, and similarly, multi-precision modular reduction are commonly considered to be amongst the most computationally expensive of the so-called basic multi-precision integer operations. These functions are often used during common communication system operations such as encryption and/or decryption. In particular, communication systems often include modular reduction in public key encryption algorithms such as RSA, El Gamal, Rabin, and Diffie-Hellman.
What is needed are methods and apparatus for providing greater throughput, functionality, and reliability for networking devices and equipment while reducing the complexity and power consumption.